Hyem.log

[백준] 21317 - 징검다리 건너기 (파이썬)

November 03, 2021

문제

문제 링크

풀이

백준 다이나믹 프로그래밍 문제집에 있는 문제인데, 재귀함수를 사용해서 풀었다!

현 위치에서 가능한 선택지가 1) 작은 점프 뛰기 2) 큰 점프 뛰기 3) 매우 큰 점프 뛰기 => 3가지이므로, 재귀함수 3번 실행을 통해 현 위치 i 마다 3번의 경우를 모두 탐색해나가는 식으로 풀었다.

처음에 문제를 똑바로 안 읽어서 놓쳤던 부분이 매우 큰 점프는 단 한 번의 기회만 주어진다는 조건이었는데, 이 부분은 매우 큰 점프를 뛰었느냐 아직 안뛰었느냐 하는 boolean 변수를 하나 추가해줘서 해결했다.

DP문제 중에 거의 처음으로 검색 없이 푼 문제라 넘나 뿌듯..

n = int(input())
small = []
big = []
for i in range(n-1):
    a, b = map(int, input().strip().split(" "))
    small.append(a)
    big.append(b)
k = int(input())


def jump(i, energy, biggest):
    # 재귀함수 종료조건 : 현위치 i가 n번 돌(인덱스상으로는 n-1)이면 result list에 지금까지 소비한 에너지 추가하고 종료
    if i == n-1:
        result.append(energy)
        
    # 재귀함수 본문    
    elif i < n-1:
        jump(i+1, energy+small[i], biggest)  # 작은 점프 뛰는 경우
        jump(i+2, energy+big[i], biggest)  # 큰 점프 뛰는 경우
        if biggest == False:  # (아직 매우 큰 점프 안 뛰었을때만) 매우 큰 점프 뛰는 경우
            jump(i+3, energy+k, True)


result = []
jump(0, 0, False)
print(min(result))  # n번 돌에 도달하는 모든 경우의 에너지들 중 최솟값 출력
Written by@[hyem]
Hyem's Dev Note

GitHub